/**
 * 基数排序 （桶排序思想的一种）
 * 思路 ： 先按个位排序，再按十位排序，再按百位排序 
 * 优化思路： 可以用一个位置数组优化代码
 */

Array.prototype.cardinal = function(){
      let maxEle = Math.max(...this);
      let mexLenth = maxEle.toString().length;
      let arr = [0,0,0,0,0,0,0,0,0,0];
      let result = this
      
      for(let i = 1 ; i<= mexLenth ; i++){
           
           // 获取每一个位置下标出现的个数
           for(let j = 0; j < result.length; j++){
              let dighit = Math.floor(((result[j] %(Math.pow(10,i))) / Math.pow(10,i-1)));  // 获取对应个位 十位 百位 的数
              arr[dighit]++; 
           }
           // 转换成位置数组
           for(let k = 1; k < arr.length ; k ++){
               arr[k] = arr[k] + arr[k-1]
           }
           let res = new Array(result.length)
           for(let j = result.length - 1 ; j >=0  ; j--){
               let dighit = Math.floor(((result[j] %(Math.pow(10,i))) / Math.pow(10,i-1))); 
               let index = arr[dighit]-1;
               arr[dighit]--;
               res[index] =  result[j];;
           }
           result = res;
           arr = [0,0,0,0,0,0,0,0,0,0]
      }
    
      return result
      

      
}


let a = [11,22,33,44,55,66,77,888,1,33,44];

console.log(a.cardinal())

